package com.leetcode;

//12^2

public class Pow
{
	public static void main(String[] args)
	{
		Pow p = new Pow();
		System.out.println(p.pow(13, 2));
	}

	public double pow(double x, int n)
	{
		if (n == 0)
			return 1;
		if (n == 1)
			return x;

		boolean negative = false;
		if (n < 0)
		{
			negative = true;
			n = -n;
		}

		// apply divide conquer algorithm
		double r = pow(x, n / 2);
		r = r * r;
		if (n % 2 != 0)
			r *= x;

		if (negative)
			r = 1 / r;

		return r;
	}
}
